package com.jack.leetcode.eachproblem_2020;

public class 冗余连接2 {

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int len = edges.length;
        int[] inDegree = new int[len + 1];
        for(int i = 0;i < len;i++){
            inDegree[edges[i][1]]++;
        }

        for(int i = len - 1;i >= 0;i--){
            if(inDegree[edges[i][1]] == 2){
                if(!judgeCircle(edges, len, i)){
                    return edges[i];
                }
            }
        }

        for(int i = len - 1;i >= 0;i--){
            if(inDegree[edges[i][1]] == 1){
                if(!judgeCircle(edges, len, i)){
                    return edges[i];
                }
            }
        }

        return new int[2];
    }

    private boolean judgeCircle(int[][] edges, int len, int removeEdgeIndex){
        UnionFind unionFind = new UnionFind(len + 1);
        for(int i = 0;i < len;i++){
            if(i == removeEdgeIndex){
                continue;
            }
            if(!unionFind.union(edges[i][0], edges[i][1])){
                return true;
            }
        }
        return false;
    }

    private class UnionFind{
        private int[] parent;

        UnionFind(int len){
            parent = new int[len];
            for(int i = 0;i < len;i++){
                parent[i] = i;
            }
        }

        private int find(int x){
            while(x != parent[x]){
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public boolean union(int x, int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY){
                return false;
            }
            parent[rootX] = rootY;
            return true;
        }
    }
}
